# 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
# 
#  
# 
#  注意： 
# 
#  
#  对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
#  如果 s 中存在这样的子串，我们保证它是唯一的答案。 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "ADOBECODEBANC", t = "ABC"
# 输出："BANC"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "a", t = "a"
# 输出："a"
#  
# 
#  示例 3: 
# 
#  
# 输入: s = "a", t = "aa"
# 输出: ""
# 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
# 因此没有符合条件的子字符串，返回空字符串。 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length, t.length <= 10⁵ 
#  s 和 t 由英文字母组成 
#  
# 
#  
# 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1500 👎 0
import math
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_count = {}
        s_count = {}

        def has_all():
            for k, v in t_count.items():
                if s_count.get(k, 0) < v:
                    return False
            return True

        for c in t:
            t_count[c] = t_count.get(c, 0) + 1

        ans_len, ans_l, ans_r = math.inf, -1, -1
        l, r = 0, 0
        n = len(s)
        while r < n:
            if s[r] in t_count:
                s_count[s[r]] = s_count.get(s[r], 0) + 1
            while has_all() and l <= r:
                if r - l + 1 < ans_len:
                    ans_len = r - l + 1
                    ans_l = l
                    ans_r = r
                if s[l] in t_count:
                    s_count[s[l]] = s_count.get(s[l], 0) - 1
                l += 1
            r += 1
        return '' if ans_l == -1 else s[ans_l: ans_r + 1]


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
滑动窗口: 右指针扩大搜索范围, 找全之后左指针缩小搜索范围
可能出现重复, 故用dict储存出现次数
"""

# def minWindow(self, s: str, t: str) -> str:
#     t_count = {}
#     s_count = {}
#     # 统计目标字符串中字符出现的个数
#     for c in t:
#         t_count[c] = t_count.get(c, 0) + 1
#
#     def has_all():
#         for k, v in t_count.items():
#             if s_count.get(k, 0) < v:
#                 return False
#         return True
#
#     l, r = 0, 0
#     s_len = len(s)
#     ans_len, ans_l, ans_r = math.inf, -1, -1
#     while r < s_len:
#         # 是目标字符串, 加入统计
#         if r < s_len and s[r] in t_count:
#             s_count[s[r]] = s_count.get(s[r], 0) + 1
#         # 包含所有时缩减窗口
#         while has_all() and l <= r:
#             # 找到更短的串, 更新结果
#             if r - l + 1 < ans_len:
#                 ans_len = r - l + 1
#                 ans_l = l
#                 ans_r = r
#             # 缩减窗口
#             if s[l] in t_count:
#                 s_count[s[l]] = s_count.get(s[l], 0) - 1
#             l += 1
#         # 移动窗口右边界
#         r += 1
#     return '' if ans_l == -1 else s[ans_l:ans_r + 1]


if __name__ == '__main__':
    s = Solution()
    source1 = 'ADOBECODEBANC'
    t1 = 'ABC'
    r1 = s.minWindow(source1, t1)
    assert r1 == 'BANC', r1
    source2 = 'a'
    t2 = 'a'
    r2 = s.minWindow(source2, t2)
    assert r2 == 'a', r2
    source3 = 'ab'
    t3 = 'a'
    r3 = s.minWindow(source3, t3)
    assert r3 == 'a', r3
